Of critical importance in the operation of communications networks is the speed at which information is exchanged through and between the communications networks. The information, e.g., data, is typically exchanged in modern-day communications networks through the routing of so-called packets. Thus, it is not surprising that one area in which a significant amount of effort has been directed is the study and modeling of communications networks from a packet routing perspective. For example, M. Andrews et al., "Universal Stability Results for Greedy Contention-Resolution Protocols", In Proceedings of the 37.sup.th Annual Symposium on Foundations of Computer Science, pp. 380-389, Burlington, Vt., October, 1996, is directed at the study of communications networks in which packets are generated at so-called "nodes" of the network and routed in discrete time steps across so-called "edges" of the network. One widely recognized critical issue in the modeling of such communications networks is the "stability" of the network. In the communications network arts, "network stability" is typically defined in terms of whether the number of packets in the network will remain bounded, as the network operates for an arbitrarily long period of time. That is, if the number of packets remains bounded over time the network is said to be stable.
Two related switching theory concepts which impact network stability are so-called "input blocking" and "output blocking". In short, input blocking is where a particular packet is blocked by another packet which requires the same input to a particular switch. That is, one packet's access to an input is "blocked" by a second packet. In contrast, output blocking is where a particular packet is blocked by another packet which requires the same output to a particular switch. Indeed, analyses of both input blocking and output blocking on a single switch is common in the switching theory arts. For example, M. J. Karol et al., "Input Versus Output Queueing on a Space-Division Packet Switch", In IEEE Transactions on Communications, 35(12):1347-1356, December, 1987, describes a queueing-theoretic approach to quantify the degradation in switch performance in the presence of input blocking. One recognized leading contributor to low switch utilization in this context is so-called head-of-line ("HOL") blocking. HOL is a situation in which a packet at the head of a first-in-first-out ("FIFO") queue used in the switch is output-blocked thereby blocking other packets in the FIFO queue. A number of techniques have been developed which are directed at reducing the effects of HOL thereby increasing individual switch utilization. For example, N. W. McKeown et al., "Achieving 100% Throughput in an Input-Queued Switch", In Proceedings of IEEE INFOCOM, pp. 296-302, San Francisco, Calif., March, 1996, describes an input-queued switch having a separate FIFO queue for each output at each input which facilitates an increased switch throughput thereby minimizing the HOL effects. Thus, the prior art is replete with various studies, models, techniques, and the like which examine the effect of input and output blocking in the context of switching theory but not in the context of network stability.
However, A. Borodin et al., "Adversarial Queueing Theory", In Proceedings of the 28.sup.th Annual ACM Symposium on Theory of Computing, pp. 376-385, Philadelphia, Pa., May, 1996, describes a so-called "adversarial injection model" for networks which can be applied in both the input and output blocking context. In accordance with this injection model, a so-called "adversary" injects packets into a network over some time interval. The adversary chooses the time at which packets are injected and the individual paths that the injected packets must follow as the packets traverse the network. Typically, the injection of packets by the adversary runs counter to providing network stability. Borodin et al., supra., and Andrews et al., supra., examine the adversarial model and its related effects from a mainly output blocking perspective. Further, in these studies and related protocols, situations are permitted for the routing of two packets that require the same input to a switch. Such a situation is not allowed in the context of a network which is subject to both input and output blocking, and where network stability is a critical issue.
However, the study of network stability in the presence of both input blocking and output blocking has not garnered a great deal of examination. In the past, the prevailing practice was to design switches so that input blocking does not occur. Further, in the past, switching speed was typically must faster than link speed so input blocking was not a major problem. As such, the examination of networks subject to both input and output blocking was not a major area for study. However, current communications switches have become much larger and switching speed is becoming more of a bottleneck and, therefore, can significantly impact the effective transmission of packets through an entire network in the presence of both input and output blocking. Therefore, a need exists for providing a communications technique which increases network stability in the presence of both input and output blocking.